package com.leetcode.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/19
 * @description:	234. 回文链表
 * A
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 * 进阶：
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/palindrome-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PalindromeLinkedList234A {

	/**
	 * todo:O(n) 时间复杂度--意味着能够用多次循环，但是不能嵌套循环！
	 * todo:此题思路：1.通过双指针确定中点；2.从中点进行链表反转；3.从短的中段进行链表遍历。
	 * @param head
	 * @return
	 */
	public boolean isPalindrome(ListNode head) {
		if(head==null||head.next==null){
			return true;
		}
		ListNode sn=head;
		ListNode fn=head;
		///1.找到中点或者中点的【后】一个位置
		while(fn!=null&&fn.next!=null){
			sn=sn.next;
			fn=fn.next.next;
		}
		///2.将后面进行反转
		ListNode temp=null;
		///pre 为反转后的节点
		ListNode pre=null;
		while (sn!=null){
			temp=sn.next;
			sn.next=pre;
			pre=sn;
			sn=temp;
		}
		ListNode seqNode=head;
		while (pre!=null){
			if (seqNode.val!=pre.val){
				return false;
			}
			seqNode=seqNode.next;
			pre=pre.next;
		}
		return true;
	}
}
